import java.util.*;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2020/8/2 上午 09:48
 */
public class month2008 {

    public void flatten(TreeNode root) {

    }

    public int countGoodTriplets(int[] arr, int a, int b, int c) {
        int cnt = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                for (int k = j + 1; k < arr.length; k++) {
                    if (Math.abs(arr[i] - arr[j]) <= a) {
                        if (Math.abs(arr[j] - arr[k]) <= b) {
                            if (Math.abs(arr[i] - arr[k]) <= c) {
                                cnt++;
                            }
                        }
                    }
                }
            }
        }
        return cnt;
    }

    public int getWinner(int[] arr, int k) {
        int[] tempArr = new int[arr.length];
        System.arraycopy(arr, 0, tempArr, 0, arr.length);
        Arrays.sort(tempArr);
        int maxNum = tempArr[arr.length - 1];
        if (k > arr.length) {
            return maxNum;
        }
        int winTime = 0, winNum = -1;
        while (winTime < k) {
            if (arr[0] < arr[1]) {
                if (winNum == arr[1]) {
                    winTime++;
                } else {
                    winTime = 1;
                }
                winNum = arr[1];
                swap(arr, 0);
            } else {
                if (winNum == arr[0]) {
                    winTime++;
                } else {
                    winTime = 1;
                }
                winNum = arr[0];
                swap(arr, 1);
            }
        }
        return winNum;
    }

    private void swap(int[] arr, int i) {
        int temp = arr[i];
        if (arr.length - 1 - i >= 0) {
            System.arraycopy(arr, i + 1, arr, i, arr.length - 1 - i);
        }
        arr[arr.length - 1] = temp;
    }

    public int minSwaps(int[][] grid) {
        int[] temp = new int[grid.length];
        for (int i = 0; i < grid.length; i++) {
            int count = 0;
            for (int j = grid[0].length - 1; j >= 0; j--) {
                if (grid[i][j] == 0) {
                    count++;
                } else {
                    break;
                }
            }
            temp[i] = count;
        }
        int count = 0, j;
        int length = temp.length;
        for (int i = 0; i < length; i++) {
            boolean flag = true;
            for (j = i; j < length; j++) {
                if (temp[j] >= length - i - 1) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return -1;
            }
            for (int k = j; k > i; k--) {
                swap(temp, k, k - 1);
                count++;
            }
        }
        return count;
    }

    public void swap(int[] f, int i, int j) {
        int temp = f[i];
        f[i] = f[j];
        f[j] = temp;
    }

    public int maxSum(int[] nums1, int[] nums2) {
        return 0;
    }

    private TreeNode nodeOne, nodeTwo, nodePre;

    public void recoverTree(TreeNode root) {
        inOrder(root);
        int tempVal = nodeOne.val;
        nodeOne.val = nodeTwo.val;
        nodeTwo.val = tempVal;
    }

    private void inOrder(TreeNode root) {
        if (root == null || (nodeOne != null && nodeTwo != null)) {
            return;
        }
        inOrder(root.left);
        if (nodePre != null && nodePre.val > root.val) {
            if (nodeOne == null) {
                nodeOne = nodePre;
            }
            nodeTwo = root;
        }
        nodePre = root;
        inOrder(root.right);
    }

    public void recoverTree2(TreeNode root) {
        TreeNode x = null, y = null, pred = null, predecessor = null;
        while (root != null) {
            if (root.left != null) {
                // predecessor 节点就是当前 root 节点向左走一步，然后一直向右走至无法走为止
                predecessor = root.left;
                while (predecessor.right != null && predecessor.right != root) {
                    predecessor = predecessor.right;
                }
                // 让 predecessor 的右指针指向 root，继续遍历左子树
                if (predecessor.right == null) {
                    predecessor.right = root;
                    root = root.left;
                }
                // 说明左子树已经访问完了，我们需要断开链接
                else {
                    if (pred != null && root.val < pred.val) {
                        y = root;
                        if (x == null) {
                            x = pred;
                        }
                    }
                    pred = root;
                    predecessor.right = null;
                    root = root.right;
                }
            }
            // 如果没有左孩子，则直接访问右孩子
            else {
                if (pred != null && root.val < pred.val) {
                    y = root;
                    if (x == null) {
                        x = pred;
                    }
                }
                pred = root;
                root = root.right;
            }
        }
        swap(x, y);
    }

    public void swap(TreeNode x, TreeNode y) {
        int tmp = x.val;
        x.val = y.val;
        y.val = tmp;
    }

    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        boolean[][] visited = new boolean[image.length][image[0].length];
        drawImage(image, visited, sr, sc, image[sr][sc], newColor);
        return image;
    }

    private void drawImage(int[][] image, boolean[][] visited, int sr, int sc, int oldColor, int newColor) {
        if (sr < 0 || sr > image.length || sc < 0 || sc > image[0].length) {
            return;
        }
        if (visited[sr][sc]) {
            return;
        }
        visited[sr][sc] = true;
        if (image[sr][sc] == oldColor) {
            image[sr][sc] = newColor;
        }
        drawImage(image, visited, sr - 1, sc, oldColor, newColor);
        drawImage(image, visited, sr - 1, sc, oldColor, newColor);
        drawImage(image, visited, sr, sc - 1, oldColor, newColor);
        drawImage(image, visited, sr, sc + 1, oldColor, newColor);
    }

    public boolean threeConsecutiveOdds(int[] arr) {
        int count = 0;
        for (int i : arr) {
            if (i % 2 == 1) {
                count++;
            } else {
                count = 0;
            }
            if (count == 3) {
                return true;
            }
        }
        return false;
    }

    public int minOperations(int n) {
        int start = 0, end = n - 1, res = 0;
        while (start < end) {
            int before = start * 2 + 1;
            int after = end * 2 + 1;
            res += (after - before) / 2;
            start++;
            end--;
        }
        return res;
    }

    public int maxDistance(int[] xs, int m) {
        Arrays.sort(xs);
        int left = 0;
        int right = inf;
        while (left < right) {
            int minDistance = (left + right + 1) / 2;
            if (check(xs, m, minDistance)) {
                left = minDistance;
            } else {
                right = minDistance - 1;
            }
        }
        return left;
    }

    int inf = (int) 1e9;

    public boolean check(int[] xs, int m, int minDistance) {
        int lastPosition = -inf;
        for (int x : xs) {
            if (x - lastPosition >= minDistance) {
                m--;
                lastPosition = x;
            }
        }
        return m <= 0;
    }

    private final Map<Integer, Integer> cache = new HashMap<>();

    public int minDays(int n) {
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        if (cache.containsKey(n)) {
            return cache.get(n);
        }
        int res = Math.min(minDays(n / 2) + n % 2 + 1, minDays(n / 3) + n % 3 + 1);
        cache.put(n, res);
        return res;
    }

    public List<Integer> mostVisited(int n, int[] rounds) {
        TreeMap<Integer, Integer> treeMap = new TreeMap<>();
        int part = rounds[0];
        for (int round : rounds) {
            while (true) {
                part %= n;
                Integer orDefault = treeMap.getOrDefault(part, 0);
                treeMap.put(part, ++orDefault);
                if (part == (round % n)) {
                    part++;
                    break;
                }
                part++;
            }
        }
        int maxPart = 0;
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (Map.Entry<Integer, Integer> entry : treeMap.entrySet()) {
            Integer key = entry.getKey();
            Integer value = entry.getValue();
            maxPart = Math.max(maxPart, value);
            List<Integer> orDefault = map.getOrDefault(value, new ArrayList<>());
            orDefault.add(key == 0 ? n : key);
            map.put(value, orDefault);
        }
        List<Integer> ret = map.get(maxPart);
        ret.sort(null);
        return ret;
    }

    public int maxCoins(int[] piles) {
        Arrays.sort(piles);
        int total = 0;
        int index = piles.length - 2;
        for (int i = 0; i < piles.length / 3; i++) {
            total += piles[index];
            index -= 2;
        }
        return total;
    }

    public static void main(String[] args) {
        month2008 month2008 = new month2008();
        month2008.mostVisited(2, new int[]{2, 1, 2, 1, 2, 1, 2, 1, 2});
    }

}
